A linear feedback shift register (LFSR) is a shift register whose input bit is a linear function of its previous state. LFSRs are commonly used in a number of different applications including generating pseudo-random noise sequences, cyclic redundancy checks (CRC), forward error-correction (FEC), cryptography, etc. The LFSR divides an input sequence by a polynomial implemented by the LFSR. An LFSR generally includes a shift register of one-bit memory elements and logic that performs a logical exclusive-or (XOR) of some bits of the overall shift register value with bits in a feedback path. The bit positions of the LFSR used in the XOR circuitry are referred to as taps. Taps may or may not affect the next value of the LFSR depending on respective coefficients of the polynomial implemented by the LFSR.
Two common LFSR architectures are the Fibonacci LFSR and the Galois LFSR. In the Fibonacci LFSR, values of the bits in the LFSR are filtered according to the respective coefficients of the polynomial and the filtered values are XOR'd together to provide an output. The result is also XOR'd with an input data value and shifted back into an input of the LFSR as feedback. In the Galois approach, the LFSR does not concatenate every tap to produce the feedback. Rather, an output value is filtered for each tap, according to the respective coefficient, and XOR'd with data as it is shifted between registers of the LFSR.
An LFSR can be implemented in either programmable logic or ASIC technologies. However, the Fibonacci and Galois LFSRs may utilize a large number of resources, which are generally limited for both ASICs and programmable integrated circuits (ICs).